Section: Application Domains

Packing and Covering Problems

We developed a branch-and-price algorithm for the Bin Packing Problem with Conflicts which improves on other approaches available in the literature [20] . The algorithm uses our methodological advances like the generic branching rule for the branch-and-price and the column based heuristic. One of the ingredients which contributes to the success of our method are fast algorithms we developed for solving the subproblem which is the Knapsack Problem with Conflicts. Two variants of the subproblem have been considered: with interval and arbitrary conflict graphs. The paper which presents this work is being finalized.

We have designed a new algorithm for vertex packing (equivalently stable set) in claw-free graphs [58] . Previously the best known algorithm for this problem had a running time of $O\left(n^6\right)$ (with $n$ the number of vertices in the graph) while our new algorithm runs in $O\left(n^4\right)$.

We studied a variant of the knapsack problem encountered in inventory routing problem [55] : we faced a multiple-class integer knapsack problem with setups [54] (items are partitioned into classes whose use implies a setup cost and associated capacity consumption). We showed the extent to which classical results for the knapsack problem can be generalized to this variant with setups and we developed a specialized branch-and-bound algorithm.

We studied the orthogonal knapsack problem, with the help of graph theory  [50] , [48] , [12] , [11] . Fekete and Schepers proposed to model multi-dimensional orthogonal placement problems by using an efficient representation of all geometrically symmetric solutions by a so called packing class involving one interval graph for each dimension. Though Fekete & Schepers' framework is very efficient, we have however identified several weaknesses in their algorithms: the most obvious one is that they do not take advantage of the different possibilities to represent interval graphs. We propose to represent these graphs by matrices with consecutive ones on each row. We proposed a branch-and-bound algorithm for the 2d knapsack problem that uses our 2D packing feasibility check.